#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<set>
using namespace std;

class Solution {
public:
    int movingCount(int m, int n, int k) {
        int result = 0;
        set<pair<int,int>> S;
        result += dfs(m,n,0,0,k,S);
        return result;
    }

    int dfs(int m,int n,int i,int j,int k,set<pair<int,int>>& S){
        if(i<0||i>=m||j<0||j>=n||S.find(make_pair(i,j))!=S.end()){
            return 0;
        }
        
        int result = computer(i,j,k);
        if(result){
            S.insert(make_pair(i,j));
            return result+dfs(m,n,i-1,j,k,S)+dfs(m,n,i+1,j,k,S)+dfs(m,n,i,j-1,k,S)+dfs(m,n,i,j+1,k,S);
            }
        else{
            S.insert(make_pair(i,j));
            return 0;
        }
    }
    int computer(int i,int j,int k){
        int sum = 0;
        while(i!=0){
            sum += i%10;
            i = i/10;
        }
        while(j!=0){
            sum+= j%10;
            j = j/10;
        }
        return sum <= k;
    }

};

int main(){
    Solution S;
    cout<<S.movingCount(16,8,4)<<endl;
}